
#include "stdio.h"
#include<stdio.h>
#include<stdlib.h>

/*
	根据用户的输入数据的顺序，创建一个带头结点的单链表
		并将新创建的链表 打印输出
*/
struct List * create_list_withHead()
{
	//创建一个头结点并初始化
	struct List *list =malloc(sizeof(struct List));
	list->first=NULL;//首节点
	list->last=NULL;//尾结点
	list->node_num=0;
	
	ElemType d;
	//创建保存数据的节点
	struct LNode *pnew=NULL;
	while(1)
	{
		scanf("%d",&d);
		if(d==0)
		{
			break;//退出输入条件
		}
		//为pnew分分配空间
		pnew =(struct LNode *)malloc(sizeof(struct LNode));
		pnew->data=d;//数据域
		pnew->next=NULL;//指针域
		
		//从无到有
		if(list->first==NULL)
		{
			list->first=pnew;
			list->last=pnew;
		}
		else//从少到多
		{
			//尾插法
			list->last->next=pnew;
			list->last=pnew;//last被pnew替代,即有结点接入尾结点后移
		}
		//计算链表结点个数
		list->node_num++;
	}
	return list;//返回链表的头结点
}
struct List *sort_list(struct List *list)
{
	struct LNode *pnew=NULL;//指向要摘下来的节点
	struct LNode *pc=NULL;//指向下一个要摘下来得节点
	pnew=list->first;
	pc=list->first;
	
	//断开原链表
	list->first=NULL;
	list->last=NULL;
	while(pnew)
	{
		//摘除结点
		pc=pc->next;
		pnew->next=NULL;
		//从无到有
		if(list->first==NULL)
		{
			list->first=pnew;
			list->last=pnew;
		}
		else
		{
			struct LNode *p=list->first;
			struct LNode *pre=NULL;
			while(p)
			{
				if(p->data >pnew->data)
				{
					break;
				}
				pre=p;
				p=p->next;
			}
			//没有找到
			if(p==NULL)
			{
				list->last->next=pnew;
				list->last=p;
			}
			else
			{
				//头插
				if(p==list->first)
				{
					pnew->next=list->first;
					list->first=pnew;
				}
				else
				{
					pre->next=pnew;
					pnew->next=p;
				}
			}
			
		}
		pnew=pc;
	}
	return list;
}
/*
	设A，B两个链表都是有序的，求A，B的交集，将新的交集返回
			A：1 1 2 2 3 5 6
			B: 1 1 1 2 3 4
		 -->C: 1 2 3  
*/			 
struct List *common_of_list(struct List *listA,struct List *listB)
{
	//1.创建一个新的链表C 交集并初始化
	struct List *listC=(struct List *)malloc(sizeof(struct List));
	listC->first=NULL;
	listC->last=NULL;
	listC->node_num=0;
	
	struct LNode *pa=listA->first;
	struct LNode *pb=listB->first;
	struct LNode *pnew=NULL;
	ElemType temp=0;
	
	while(pa&&pb)
	{
		if(pa->data==pb->data)
		{
			if(pa->data!=temp)
			{
				pnew=(struct LNode*)malloc(sizeof(struct LNode));
				pnew->data=pa->data;
				pnew->next=NULL;
			
				if(listC->first==NULL)
				{
					listC->first=pnew;
					listC->last=pnew;
				}
				else
				{
					//尾插法
					listC->last->next=pnew;
					listC->last=pnew;
				}
				temp=pa->data;
				listC->node_num++;
			}
			pa=pa->next;
			pb=pb->next;
		}
		else if(pa->data < pb->data)//谁小谁先往后移
		{
			pa=pa->next;
		}
		else
		{
			pb=pb->next;
		}
	}
	return listC;
}


//打印链表
void print_list(struct List *list)
{
	struct LNode * head=list->first; 
	while(head)
	{
		printf("%d ",head->data);
		head=head->next;
	}
	printf("\n");
}



